home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 2334 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  3.0 KB
  1. Path: mail2news.demon.co.uk!longbarn.demon.co.uk
  2. From: Peter Jones <pete@longbarn.demon.co.uk>
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Algorithm - intersection of lines!
  5. Date: Sat, 20 Jan 1996 15:13:52 GMT
  6. Organization: None
  7. Message-ID: <83080835wnr@longbarn.demon.co.uk>
  8. References: <4dp94nINN822@keats.ugrad.cs.ubc.ca>  <4bebi9$eik@news.infi.net> <e3f_9601030228@tor250.org> <4crl7v$bju@news.microsoft.com>
  9. Reply-To: pete@longbarn.demon.co.uk
  10. X-NNTP-Posting-Host: longbarn.demon.co.uk
  11. X-Broken-Date: Saturday, Jan 20, 1996 15.13.52
  12. X-Newsreader: Newswin Alpha 0.7
  13. X-Mail2News-Path: relay-4.mail.demon.net!post.demon.co.uk!longbarn.demon.co.uk
  14.  
  15.  
  16. The best way I can think of to approach this problem is to think of the 
  17. lines as vectors, i.e. ai+bj+ck. This way it doesn't matter whether 
  18. it's 3d or 2d (I'll asume 3d).
  19.  
  20. The equation of a line would be:
  21.  
  22.  r=p+hd
  23.  
  24. where     r=any point on the line
  25.     p=a point known to be on the line
  26.     d=a direction vector describing the line
  27.     h=a number, vary this to get different values for r
  28.  
  29. If a line , (1), passes thoug a and b, its equation would be:
  30.  
  31.     r(1)=a+h(b-a)
  32.  
  33. And if the other, (2) line passes though m and n, its equation is:
  34.  
  35.     r(2)=m+g(n-m)
  36.  
  37. For lines in 3d, there are 3 possibilities:
  38.     they are parallel, ie do not cross
  39.     they are not parallel and do not cross, ie they are skew
  40.     they are not parallel and they do cross.
  41.  
  42. For the first case, we can see if the lines are parallel by using the 
  43. cross product. If the values for all of the direction vectors comes to 
  44. 0,  then they're parallel, i.e. for ai+bj+ck a=b=c=0. If the lines are
  45. found to be parallel, then they will never cross and you can give up.
  46.  
  47. OR
  48.  
  49. The ratios of the direction vectors can be compared, and if they're the same,
  50. the lines are parallel. For example,
  51.     r(1)=i+j+k+h(3i-2j+4k)
  52.     r(2)=2i-j+3k+g(-6i+4j-8k)
  53.  
  54.     ratio of r(1)=3:-2:4
  55.     ratio of r(2)=-6:4:-8=3:-2:4
  56.      
  57.     Therefore the lines are parallel.
  58.  
  59. Next, having found the lines not to be parallel, you find out where they
  60. cross. This happens when r(1)=r(2):
  61.  
  62.     a+h(b-a)=m+g(n-m)
  63.  
  64. This may seem complicated, but because it's in vectors, we just see where
  65. the separate components of i, j, and k are equal, which gives us three
  66. simultaneous equations. You can solve these however you like, by using
  67. matrices would be one way. From these equations, we find a value of h and
  68. g, which can be used for one of the equations to find the point in question.
  69.  
  70. If no solutions can be found, then the lines are skew.
  71.  
  72. In summary, the steps are
  73.     1 : Form vector equations of the two lines.
  74.     2:  See if the lines are parallel. If not, continue.
  75. 3:  See if  the 3 simultaneous equations formed  can be
  76.      solved.
  77.  
  78. If anyone can see a problem with this solution, please tell me, because
  79. I worked it out as part of my A-Level revision, and don't want to walk
  80. into the exam thinking that this is what I want to do.
  81.  
  82. /-------------------------------------------------------------------------\
  83. | Peter Jones           pete@longbarn.demon.co.uk                         |
  84. \-------------------------------------------------------------------------/
  85.  
  86.